// https://www.lintcode.com/problem/palindromic-substrings/

public class Solution {
    /**
     * @param str: s string
     * @return: return an integer, denote the number of the palindromic substrings
     */
    public int countPalindromicSubstrings(String str) {
        // write your code here
        // dp[i][j]表示str[i:j + 1]是否为回文串。
        // 如果dp[i][j]是回文串，那么dp[i + 1][j - 1]一定也是。
        int ret = 0;
        boolean[][] dp = new boolean[str.length()][str.length()];
        for (int i = 0; i < str.length(); ++i) { // Arrays.fill只支持一维数组...
            for (int j = 0; j < str.length(); ++j) {
                dp[i][j] = false;
            }
        }
        for (int i = str.length() - 1; i >= 0; --i) {
            for (int j = i; j < str.length(); ++j) {
                if (str.charAt(i) == str.charAt(j)) {
                    if (((j - i) <= 2) || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        ++ret;
                    }
                }
            }
        }
        return ret;
    }
}